Solid-state data storage devices, which use non-volatile NAND flash memory technology, are being pervasively deployed in various computing and storage systems. In addition to one or multiple NAND flash memory chips, each solid-state data storage device must contain a controller that manages all the NAND flash memory chips. NAND flash memory cells are organized in an array-block-page hierarchy, where one NAND flash memory array is partitioned into a large number (e.g., thousands) of blocks, and each block contains a certain number of pages (e.g., 256). The size of each flash memory physical page typically ranges from 8 kB to 32 kB, and the size of each flash memory block is typically tens of MBs. Data are programmed and fetched in units of pages. However, flash memory cells must be erased before being re-programmed, and the erase operation is carried out in the unit of block (i.e., all the pages within the same block must be erased at the same time). Due to the unit size mismatch between write and erase operations, the storage device controller must carry out a garbage collection (GC) operation: Before erasing a flash memory block, the controller has to copy all the valid data from this block to other flash memory block(s). The purpose of GC is to reclaim flash memory storage space being occupied by stale flash memory pages (i.e., those flash memory pages whose content have become invalid and useless) and make them available to serve future write requests.
As a background operation, GC is transparent to end users. However, the flash memory read/write activities invoked by GC inevitably interfere with normal I/O requests. Such interference contributes to increased storage device I/O performance variation (i.e., inconsistency, unpredictability, reduced user experience, etc.). Many applications are very sensitive and intolerant to I/O performance variation, and often consider I/O performance variation as a metric that is much more important than average I/O performance.